package main

import (
	"fmt"
)

func main() {
	fmt.Println(longestPalindrome1("ababc"))
}

func longestPalindrome(s string) string {
	bytes := []byte(s)
	dpMap := make(map[int]string, len(s))
	maxLen := 0
	for k, _ := range bytes {
		for i, _ := range bytes[:k+1] {
			if isPalindrome(bytes[i : k+1]) {
				if len(bytes[i:k+1]) > maxLen {
					maxLen = len(bytes[i : k+1])
				}
				dpMap[len(bytes[i:k+1])] = string(bytes[i : k+1])
			}
		}
	}
	return dpMap[maxLen]
}

func isPalindrome(input []byte) (result bool) {
	for i := 0; i < len(input)/2; i++ {
		if input[i] != input[len(input)-1-i] {
			return false
		}
	}
	return true
}

func longestPalindrome1(s string) string {
	maxV := 0
	var maxPair []int
	dp := make([][]bool, len(s))
	for k := 0; k < len(s)-1; k++ {
		dp[k] = make([]bool, len(s))
		dp[k][k] = true
		maxV = max(maxV, 1)
		if s[k] == s[k+1] {
			dp[k][k+1] = true
			maxV = max(maxV, 2)
			maxPair = []int{k, k + 2}
		}
	}
	for Len := 3; Len < len(s); Len++ {
		for i := 0; i <= len(s)-Len; i++ {
			j := i + Len - 1
			if s[i] == s[j] && dp[i+1][j-1] {
				dp[i][j] = true
				maxV = Len
				maxPair = []int{i, j + 1}
			}
		}
	}
	if maxV == 1 {
		return string(s[0])
	} else if maxV == 0 {
		return ""
	} else {
		return s[maxPair[0]:maxPair[1]]
	}
}

func max(arg1, arg2 int) int {
	if arg1 > arg2 {
		return arg1
	}
	return arg2
}
